{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bricks Falling When Hit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hitBricks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打砖块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个 <code>m x n</code> 的二元网格<meta charset=\"UTF-8\" />&nbsp;<code>grid</code>&nbsp;，其中 <code>1</code> 表示砖块，<code>0</code> 表示空白。砖块 <strong>稳定</strong>（不会掉落）的前提是：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一块砖直接连接到网格的顶部，或者</li>\n",
    "\t<li>至少有一块相邻（4&nbsp;个方向之一）砖块<strong> 稳定 </strong>不会掉落时</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>hits</code> ，这是需要依次消除砖块的位置。每当消除&nbsp;<code>hits[i] = (rowi, coli)</code> 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 <strong>掉落</strong> 。一旦砖块掉落，它会 <strong>立即</strong> 从网格&nbsp;<code>grid</code>&nbsp;中消失（即，它不会落在其他稳定的砖块上）。</p>\n",
    "\n",
    "<p>返回一个数组 <code>result</code> ，其中 <code>result[i]</code> 表示第 <code>i</code> 次消除操作对应掉落的砖块数目。</p>\n",
    "\n",
    "<p><strong>注意</strong>，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]\n",
    "<strong>输出：</strong>[2]\n",
    "<strong>解释：</strong>网格开始为：\n",
    "[[1,0,0,0]，\n",
    " [<strong>1</strong>,1,1,0]]\n",
    "消除 (1,0) 处加粗的砖块，得到网格：\n",
    "[[1,0,0,0]\n",
    " [0,<strong>1</strong>,<strong>1</strong>,0]]\n",
    "两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：\n",
    "[[1,0,0,0],\n",
    " [0,0,0,0]]\n",
    "因此，结果为 [2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]\n",
    "<strong>输出：</strong>[0,0]\n",
    "<strong>解释：</strong>网格开始为：\n",
    "[[1,0,0,0],\n",
    " [1,<strong>1</strong>,0,0]]\n",
    "消除 (1,1) 处加粗的砖块，得到网格：\n",
    "[[1,0,0,0],\n",
    " [1,0,0,0]]\n",
    "剩下的砖都很稳定，所以不会掉落。网格保持不变：\n",
    "[[1,0,0,0], \n",
    " [<strong>1</strong>,0,0,0]]\n",
    "接下来消除 (1,0) 处加粗的砖块，得到网格：\n",
    "[[1,0,0,0],\n",
    " [0,0,0,0]]\n",
    "剩下的砖块仍然是稳定的，所以不会有砖块掉落。\n",
    "因此，结果为 [0,0] 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 200</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "\t<li><code>1 &lt;= hits.length &lt;= 4 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>hits[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>i&nbsp;</sub>&lt;= m - 1</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;y<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li>所有 <code>(x<sub>i</sub>, y<sub>i</sub>)</code> 互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bricks-falling-when-hit](https://leetcode.cn/problems/bricks-falling-when-hit/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bricks-falling-when-hit](https://leetcode.cn/problems/bricks-falling-when-hit/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,0,0],[1,1,1,0]]\\n[[1,0]]', '[[1,0,0,0],[1,1,0,0]]\\n[[1,1],[1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [0] * len(hits)\n",
    "        if m == 1:\n",
    "            return ans\n",
    "        for x, y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        def dfs(i:int, j:int)-> int:\n",
    "            if i < 0 or i == m or j < 0 or j == n or grid[i][j] != 1:\n",
    "                return 0\n",
    "            grid[i][j] = 2\n",
    "            return 1 + dfs(i + 1, j) + dfs(i - 1, j) + dfs(i, j + 1) + dfs(i, j - 1)\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                dfs(0, j)\n",
    "        def worth(i:int, j:int)-> bool:\n",
    "            return grid[i][j] == 1 and (i == 0 or (i > 0 and grid[i - 1][j] == 2) or (i < m - 1 and grid[i + 1][j] == 2) or (j > 0 and grid[i][j - 1] == 2) or (j < n - 1 and grid[i][j + 1] == 2))\n",
    "        for i in range(len(hits) - 1, - 1, -1):\n",
    "            x, y = hits[i]\n",
    "            grid[x][y] += 1\n",
    "            if worth(x, y):\n",
    "                ans[i] = dfs(x, y) - 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [-1]*len(hits)\n",
    "        def dfs(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                grid[x][y] = 2\n",
    "                ans = 1 + dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1)\n",
    "                return ans\n",
    "            return 0\n",
    "        def is_stable(x, y):\n",
    "            if x == 0: return True\n",
    "            if x + 1 < m and grid[x + 1][y] == 2: return True\n",
    "            if x - 1 >= 0 and grid[x - 1][y] == 2: return True\n",
    "            if y + 1 < n and grid[x][y + 1] == 2: return True\n",
    "            if y - 1 >= 0 and grid[x][y - 1] == 2: return True\n",
    "            return False\n",
    "        # 模拟最终的残局\n",
    "        for x, y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        # 标记稳定砖块。 注意不标记被打掉的砖块，因此这一步需要在“模拟最终的残局”之后\n",
    "        for y in range(n):\n",
    "            dfs(0, y)\n",
    "        # 倒推\n",
    "        for i in range(len(hits) - 1, -1,-1):\n",
    "            x, y = hits[i]\n",
    "            grid[x][y] += 1\n",
    "            # 如果不稳定，打掉也没啥影响\n",
    "            if not is_stable(x, y) or grid[x][y] == 0:\n",
    "                ans[i] = 0\n",
    "            else:\n",
    "                # 否则 dfs 计算联通图大小，这里的联通指的是值为 1。\n",
    "                # 实际指的是添加了 (x,y) 砖块之后，这些值为 1 的砖块会变成稳定砖块（我们用 2 表示）\n",
    "                # 由于我们是反推，因此就是移除 (x, y) 砖块之后， 这些稳定的砖块会变成不稳定（掉落）\n",
    "                ans[i] = dfs(x, y) - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        def dfs(grid,n,m,i,j):\n",
    "            if i==-1 or i==n or j==-1 or j==m or grid[i][j]!=1:\n",
    "                return 0\n",
    "            grid[i][j] = 2\n",
    "            return 1+dfs(grid,n,m,i+1,j)+dfs(grid,n,m,i-1,j)+dfs(grid,n,m,i,j+1)+dfs(grid,n,m,i,j-1)\n",
    "        def worth(grid,i,j):\n",
    "            return grid[i][j]==1 and (i==0 or (i>0 and grid[i-1][j]==2) or (j>0 and grid[i][j-1]==2) or (i+1<len(grid) and grid[i+1][j]==2) or (j+1<len(grid[0]) and grid[i][j+1]==2))\n",
    "\n",
    "\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ans = [0]*len(hits)\n",
    "        if n==1:\n",
    "            return ans\n",
    "        for hit in hits:\n",
    "            grid[hit[0]][hit[1]] -= 1\n",
    "        for i in range(m):\n",
    "            dfs(grid,n,m,0,i)\n",
    "        for i in range(len(hits)-1,-1,-1):\n",
    "            row = hits[i][0]\n",
    "            col = hits[i][1]\n",
    "            grid[row][col] += 1\n",
    "            if worth(grid,row,col):\n",
    "                ans[i] = dfs(grid,n,m,row,col)-1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [-1]*len(hits)\n",
    "        def dfs(x, y):\n",
    "            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                grid[x][y] = 2\n",
    "                ans = 1 + dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1)\n",
    "                return ans\n",
    "            return 0\n",
    "        def is_stable(x, y):\n",
    "            if x == 0: return True\n",
    "            if x + 1 < m and grid[x + 1][y] == 2: return True\n",
    "            if x - 1 >= 0 and grid[x - 1][y] == 2: return True\n",
    "            if y + 1 < n and grid[x][y + 1] == 2: return True\n",
    "            if y - 1 >= 0 and grid[x][y - 1] == 2: return True\n",
    "            return False\n",
    "        # 模拟最终的残局\n",
    "        for x, y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        # 标记稳定砖块。 注意不标记被打掉的砖块，因此这一步需要在“模拟最终的残局”之后\n",
    "        for y in range(n):\n",
    "            dfs(0, y)\n",
    "        # 倒推\n",
    "        for i in range(len(hits) - 1, -1,-1):\n",
    "            x, y = hits[i]\n",
    "            grid[x][y] += 1\n",
    "            # 如果不稳定，打掉也没啥影响\n",
    "            if not is_stable(x, y) or grid[x][y] == 0:\n",
    "                ans[i] = 0\n",
    "            else:\n",
    "                # 否则 dfs 计算联通图大小，这里的联通指的是值为 1。\n",
    "                # 实际指的是添加了 (x,y) 砖块之后，这些值为 1 的砖块会变成稳定砖块（我们用 2 表示）\n",
    "                # 由于我们是反推，因此就是移除 (x, y) 砖块之后， 这些稳定的砖块会变成不稳定（掉落）\n",
    "                ans[i] = dfs(x, y) - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [0] * len(hits)\n",
    "        \n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                grid[x][y] = 2\n",
    "                return 1 + dfs(x-1,y) + dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)\n",
    "            return 0\n",
    "        \n",
    "        def isStable(x: int, y: int) -> bool:\n",
    "            if x == 0:\n",
    "                return True\n",
    "            if x - 1 >= 0 and grid[x-1][y] == 2:\n",
    "                return True\n",
    "            if x + 1 < m and grid[x+1][y] == 2:\n",
    "                return True\n",
    "            if y - 1 >= 0 and grid[x][y-1] == 2:\n",
    "                return True\n",
    "            if y + 1 < n and grid[x][y+1] == 2:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        for x, y in hits:\n",
    "            grid[x][y] -= 1\n",
    "\n",
    "        for y in range(n):\n",
    "            dfs(0,y)\n",
    "\n",
    "        ###注意python中按下标倒序遍历是怎样遍历的！！！\n",
    "        for i, (x, y) in enumerate(reversed(hits)):\n",
    "            grid[x][y] += 1\n",
    "            ###注意逻辑关系是或不是且！！！逻辑关系别乱！！！\n",
    "            if not isStable(x,y) or grid[x][y] == 0:\n",
    "                ans[len(hits) - i - 1] = 0\n",
    "            else:\n",
    "                ans[len(hits) - i - 1] = dfs(x,y) - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = []\n",
    "        for i in range(len(hits)):\n",
    "            ans.append(-1)\n",
    "        \n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:\n",
    "                grid[x][y] = 2\n",
    "                return 1 + dfs(x-1,y) + dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)\n",
    "            return 0\n",
    "        \n",
    "        def isStable(x: int, y: int) -> bool:\n",
    "            if x == 0:\n",
    "                return True\n",
    "            if x - 1 >= 0 and grid[x-1][y] == 2:\n",
    "                return True\n",
    "            if x + 1 < m and grid[x+1][y] == 2:\n",
    "                return True\n",
    "            if y - 1 >= 0 and grid[x][y-1] == 2:\n",
    "                return True\n",
    "            if y + 1 < n and grid[x][y+1] == 2:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(len(hits)):\n",
    "            x = hits[i][0]\n",
    "            y = hits[i][1]\n",
    "            grid[x][y] -= 1\n",
    "\n",
    "        for y in range(n):\n",
    "            dfs(0,y)\n",
    "\n",
    "        ###注意python中按下标倒序遍历是怎样遍历的！！！\n",
    "        for i in range(len(hits)-1,-1,-1):\n",
    "            x = hits[i][0]\n",
    "            y = hits[i][1]\n",
    "            grid[x][y] += 1\n",
    "            ###注意逻辑关系是或不是且！！！逻辑关系别乱！！！\n",
    "            if not isStable(x,y) or grid[x][y] == 0:\n",
    "                ans[i] = 0\n",
    "            else:\n",
    "                ans[i] = dfs(x,y) - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        def dfs(i, j):\n",
    "            if i == -1 or i == len(grid) or j == -1 or j == len(grid[0]) or grid[i][j] != 1:\n",
    "                return 0\n",
    "            grid[i][j] = 2\n",
    "            return 1 + dfs(i+1, j) + dfs(i, j+1) + dfs(i-1, j) +dfs(i, j-1)\n",
    "        def worth(i, j):\n",
    "            if grid[i][j] == 1:\n",
    "                if i == 0 or i > 0 and grid[i-1][j] == 2 or i+1 < len(grid) and grid[i+1][j] == 2 or j > 0 and grid[i][j-1] == 2 or j+1 < len(grid[0]) and grid[i][j+1] == 2:\n",
    "                    return True\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        ans = [0 for _ in range(len(hits))]\n",
    "        for val in hits:\n",
    "            grid[val[0]][val[1]] -= 1\n",
    "        for j in range(m):\n",
    "            dfs(0, j)\n",
    "        for i in range(len(hits)-1, -1, -1):\n",
    "            a = hits[i][0]\n",
    "            b = hits[i][1]\n",
    "            grid[a][b] += 1\n",
    "            if worth(a, b):\n",
    "                ans[i] = dfs(a, b) - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        rowCount=len(grid)\n",
    "        colCount=len(grid[0])\n",
    "        visited=set()\n",
    "        DIRS=[[1,0],[-1,0],[0,1],[0,-1]]\n",
    "\n",
    "        def dfs(r: int, c: int) -> int:\n",
    "            \n",
    "            if r<0 or r>=rowCount or c<0 or c>= colCount or grid[r][c]!=1:\n",
    "                return 0\n",
    "\n",
    "            grid[r][c]=2\n",
    "\n",
    "            return dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)+1\n",
    "        \n",
    "        def isConnected(r: int, c: int) -> bool:\n",
    "\n",
    "            if r==0: return True\n",
    "\n",
    "            for d in DIRS:\n",
    "                x=r+d[0]\n",
    "                y=c+d[1]\n",
    "                if x >=0 and x<rowCount and y>=0 and y<colCount and grid[x][y]==2:\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        for hit in hits:\n",
    "            grid[hit[0]][hit[1]]-=1\n",
    "\n",
    "        visited=set()\n",
    "        for i in range(colCount):\n",
    "            if grid[0][i]==1:\n",
    "                dfs(0,i)\n",
    "        \n",
    "        hitCount=len(hits)\n",
    "        res=[]\n",
    "        for ihit in range(hitCount-1,-1,-1):\n",
    "            r,c=hits[ihit][0], hits[ihit][1]\n",
    "            grid[r][c]+=1\n",
    "            if grid[r][c]==0: \n",
    "                res.append(0)\n",
    "                continue            \n",
    "            if grid[r][c]==1 and isConnected(r,c):\n",
    "                res.append(dfs(r,c)-1)\n",
    "            else:                        \n",
    "                res.append(0)\n",
    "        \n",
    "        return res[::-1]\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.f = list(range(n)) # father\n",
    "        self.sz = [1] * n # size\n",
    "    def find(self, x):\n",
    "        if x == self.f[x]:\n",
    "            return x\n",
    "        newf = self.find(self.f[x])\n",
    "        self.f[x] = newf\n",
    "        return self.f[x]\n",
    "    def merge(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        self.f[fx] = fy # 没有深度，所以不按深度合并。\n",
    "        self.sz[fy] += self.sz[fx]\n",
    "    \n",
    "    def size(self, x):\n",
    "        return self.sz[self.find(x)]\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        h, w = len(grid), len(grid[0])\n",
    "        uf = UnionFind(h * w + 1) # 最后一个节点是虚拟节点，代表连接着上边界。\n",
    "        status = [row[:] for row in grid]\n",
    "        for i,j in hits:\n",
    "            status[i][j] = 0\n",
    "        \n",
    "        # init uf\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if status[i][j] == 1:\n",
    "                    if i == 0:\n",
    "                        uf.merge(h * w, i * w + j)\n",
    "                    if i > 0 and status[i - 1][j] == 1:\n",
    "                        uf.merge(i * w + j, (i - 1) * w + j)\n",
    "                    if j > 0 and status[i][j - 1] == 1:\n",
    "                        uf.merge(i * w + j, i * w + j - 1)\n",
    "\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        ret = [0] * len(hits)\n",
    "        # 逆序遍历被打的砖块，一块块拼回去计算拼上的数量。\n",
    "        for i in range(len(hits) - 1, -1, -1):\n",
    "            r, c = hits[i]\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            prev = uf.size(h * w)\n",
    "\n",
    "            if r == 0:\n",
    "                uf.merge(c, h * w) # r(0) * w + c\n",
    "            for dr,dc in dirs:\n",
    "                nr, nc = r + dr, c + dc\n",
    "                if 0 <= nr < h and 0 <= nc < w and status[nr][nc] == 1:\n",
    "                    uf.merge(r * w + c, nr * w + nc)\n",
    "            \n",
    "            size = uf.size(h * w)\n",
    "            ret[i] = max(0, size - prev - 1)# 因为被打的砖块不计算在内\n",
    "            status[r][c] = 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        status = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                status[i][j] = grid[i][j]\n",
    "        for i, j in hits:\n",
    "            status[i][j] = 0\n",
    "        \n",
    "        uf = UF(m*n+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if status[i][j] == 1:\n",
    "                    idx = i * n + j\n",
    "                    if i == 0:\n",
    "                        uf.union(m*n, idx)\n",
    "                    elif status[i-1][j] == 1:\n",
    "                        uf.union(idx, idx-n)\n",
    "                    if j > 0 and status[i][j-1] == 1:\n",
    "                        uf.union(idx, idx-1)\n",
    "\n",
    "        ans = []\n",
    "        for i, j in reversed(hits):\n",
    "            if grid[i][j] == 0:\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            status[i][j] = 1\n",
    "            pre_size = uf.get_size(m*n)\n",
    "            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                if x < 0:\n",
    "                    uf.union(i*n+j, m*n)\n",
    "                elif 0 <= x < m and 0 <= y < n and status[x][y] == 1:\n",
    "                    uf.union(x*n+y, i*n+j)\n",
    "            cur_size = uf.get_size(m*n)\n",
    "            ans.append(max(0, cur_size - pre_size - 1))\n",
    "\n",
    "        return ans[::-1]\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, N):\n",
    "        self.parent = list(range(N))\n",
    "        self.size = [1] * N\n",
    "\n",
    "    def find(self, x):\n",
    "        if x == self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return\n",
    "        self.parent[rx] = ry\n",
    "        self.size[ry] += self.size[rx]\n",
    "\n",
    "    def get_size(self, x):\n",
    "        return self.size[self.find(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.f = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] == x:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        fx = self.find(x)\n",
    "        fy = self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        self.f[fx] = fy\n",
    "        self.sz[fy] += self.sz[fx]\n",
    "\n",
    "    def size(self, x):\n",
    "        return self.sz[self.find(x)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid, hits):\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "\n",
    "        uf = UnionFind(h * w + 1)\n",
    "        status = [row[:] for row in grid]\n",
    "        \n",
    "        for hit in hits:\n",
    "            status[hit[0]][hit[1]] = 0\n",
    "\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if status[i][j] == 1:\n",
    "                    if i == 0:\n",
    "                        uf.merge(h * w, i * w + j)\n",
    "                    if i > 0 and status[i - 1][j] == 1:\n",
    "                        uf.merge(i * w + j, (i - 1) * w + j)\n",
    "                    if j > 0 and status[i][j - 1] == 1:\n",
    "                        uf.merge(i * w + j, i * w + j - 1)\n",
    "\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        ret = [0] * len(hits)\n",
    "        for i in range(len(hits) - 1, -1, -1):\n",
    "            r, c = hits[i]\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            prev = uf.size(h * w)\n",
    "\n",
    "            if r == 0:\n",
    "                uf.merge(c, h * w)\n",
    "\n",
    "            for dr, dc in directions:\n",
    "                nr = r + dr\n",
    "                nc = c + dc\n",
    "                \n",
    "                if 0 <= nr < h and 0 <= nc < w:\n",
    "                    if status[nr][nc] == 1:\n",
    "                        uf.merge(r * w + c, nr * w + nc)\n",
    "\n",
    "            size = uf.size(h * w)\n",
    "            ret[i] = max(0, size - prev - 1)\n",
    "            status[r][c] = 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        uf = UnionFind(m*n + 1)\n",
    "\n",
    "        for x,y in hits:\n",
    "            if grid[x][y] == 1:\n",
    "                grid[x][y] = 0\n",
    "            else:\n",
    "                grid[x][y] = -1\n",
    "\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.union(j, m*n)\n",
    "    \n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if grid[i - 1][j] == 1:\n",
    "                        uf.union(i*n + j, (i - 1)*n + j)\n",
    "                    if j > 0 and grid[i][j - 1] == 1:\n",
    "                        uf.union(i*n + j - 1, i*n + j)\n",
    "        ans = []\n",
    "\n",
    "        for x,y in hits[::-1]:\n",
    "            if grid[x][y] == -1:\n",
    "                grid[x][y] = 0\n",
    "                ans.append(0)\n",
    "                continue\n",
    "            # 添加前顶层根结点子节点个数\n",
    "            a = uf.get_size(m*n)\n",
    "            # 添加节点\n",
    "            grid[x][y] = 1\n",
    "            if x == 0:\n",
    "                uf.union(y, m*n)\n",
    "            for nx,ny in (x + 1,y),(x - 1,y),(x,y + 1),(x,y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:\n",
    "                    uf.union(x*n + y, nx*n + ny)\n",
    "            b = uf.get_size(m *n)\n",
    "            ans.append(max(0,b - a - 1))\n",
    "        \n",
    "        return ans[::-1]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1]*n\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self,x,y):\n",
    "        a,b = self.find(x),self.find(y)\n",
    "        if a != b:\n",
    "            self.fa[a] = b\n",
    "            self.size[b] += self.size[a]\n",
    "    \n",
    "    def get_size(self,x):\n",
    "        return self.size[self.find(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.f = [i for i in range(n)]\n",
    "        self.sz = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] == x:\n",
    "            return x\n",
    "        self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "\n",
    "    def merge(self, x, y):\n",
    "        fx = self.find(x)\n",
    "        fy = self.find(y)\n",
    "        if fx == fy:\n",
    "            return\n",
    "        self.f[fx] = fy\n",
    "        self.sz[fy] += self.sz[fx]\n",
    "\n",
    "    def size(self, x):\n",
    "        return self.sz[self.find(x)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid, hits):\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "\n",
    "        uf = UnionFind(h * w + 1)\n",
    "        status = [row[:] for row in grid]\n",
    "        \n",
    "        for hit in hits:\n",
    "            status[hit[0]][hit[1]] = 0\n",
    "\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if status[i][j] == 1:\n",
    "                    if i == 0:\n",
    "                        uf.merge(h * w, i * w + j)\n",
    "                    if i > 0 and status[i - 1][j] == 1:\n",
    "                        uf.merge(i * w + j, (i - 1) * w + j)\n",
    "                    if j > 0 and status[i][j - 1] == 1:\n",
    "                        uf.merge(i * w + j, i * w + j - 1)\n",
    "\n",
    "        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        ret = [0] * len(hits)\n",
    "        for i in range(len(hits) - 1, -1, -1):\n",
    "            r, c = hits[i]\n",
    "            if grid[r][c] == 0:\n",
    "                continue\n",
    "            prev = uf.size(h * w)\n",
    "\n",
    "            if r == 0:\n",
    "                uf.merge(c, h * w)\n",
    "\n",
    "            for dr, dc in directions:\n",
    "                nr = r + dr\n",
    "                nc = c + dc\n",
    "                \n",
    "                if 0 <= nr < h and 0 <= nc < w:\n",
    "                    if status[nr][nc] == 1:\n",
    "                        uf.merge(r * w + c, nr * w + nc)\n",
    "\n",
    "            size = uf.size(h * w)\n",
    "            ret[i] = max(0, size - prev - 1)\n",
    "            status[r][c] = 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\r\n",
    "    def __init__(self,n) -> None:\r\n",
    "        self.p=list(range(n))\r\n",
    "        self.sz=[1]*n\r\n",
    "    \r\n",
    "    def find(self,x):\r\n",
    "        if x!=self.p[x]:\r\n",
    "            self.p[x]=self.find(self.p[x])\r\n",
    "        return self.p[x]\r\n",
    "\r\n",
    "    def merge(self,x,y):\r\n",
    "        px,py=self.find(x),self.find(y)\r\n",
    "        if px==py:\r\n",
    "            return\r\n",
    "        self.p[py]=px\r\n",
    "        self.sz[px]+=self.sz[py]\r\n",
    "    \r\n",
    "    def size(self,x):\r\n",
    "        return self.sz[self.find(x)]\r\n",
    "    \r\n",
    "class Solution:\r\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\r\n",
    "        R,C=len(grid),len(grid[0])\r\n",
    "        def index(r,c):\r\n",
    "            return r*C+c\r\n",
    "        \r\n",
    "        status=[row.copy() for row in grid]\r\n",
    "        for r,c in hits:\r\n",
    "            status[r][c]=0\r\n",
    "        \r\n",
    "        union=Union(R*C+1)\r\n",
    "\r\n",
    "        root=R*C\r\n",
    "        for r in range(R):\r\n",
    "            for c in range(C):\r\n",
    "                if status[r][c]==0:\r\n",
    "                    continue\r\n",
    "                idx=index(r,c)\r\n",
    "                if r==0:\r\n",
    "                    union.merge(c,root)\r\n",
    "                if r>0 and status[r-1][c]:\r\n",
    "                    union.merge(idx,index(r-1,c))\r\n",
    "                if c>0 and status[r][c-1]:\r\n",
    "                    union.merge(idx,index(r,c-1))\r\n",
    "        \r\n",
    "        dirs=[-1,0,1,0,-1]\r\n",
    "        ret=[0]*len(hits)\r\n",
    "        for i in range(len(hits)-1,-1,-1):\r\n",
    "            r,c=hits[i]\r\n",
    "            if grid[r][c]==0:\r\n",
    "                continue\r\n",
    "            idx=index(r,c)\r\n",
    "            prev=union.size(root)\r\n",
    "            if r==0:\r\n",
    "                union.merge(idx,root)\r\n",
    "            for d in range(4):\r\n",
    "                nr,nc=r+dirs[d],c+dirs[d+1]\r\n",
    "                if nr<0 or nr==R or nc<0 or nc==C or status[nr][nc]==0:\r\n",
    "                    continue\r\n",
    "                union.merge(idx,index(nr,nc))\r\n",
    "            cur=union.size(root)\r\n",
    "            ret[i]=max(0,cur-prev-1)\r\n",
    "            status[r][c]=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import *\n",
    "from heapq import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [x for x in range(n)]\n",
    "        self.size = [1 for _ in range(n)]\n",
    "        self.n = n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def Find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.Find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def Union(self, x: int, y: int) -> bool:\n",
    "        root_x = self.Find(x)\n",
    "        root_y = self.Find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] > self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "\n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        return self.Find(x) == self.Find(y)\n",
    "\n",
    "    def members(self, x):\n",
    "        root = self.Find(x)\n",
    "        return [i for i in range(self.n) if self.Find(i) == root]\n",
    "    \n",
    "    def roots(self):\n",
    "        return [i for i, x in enumerate(self.parent) if i == x]\n",
    "    \n",
    "    def group_count(self):\n",
    "        return len(self.roots())\n",
    "    \n",
    "    def all_group_members(self):\n",
    "        mp = defaultdict(list)\n",
    "        for member in range(self.n):\n",
    "            mp[self.Find(member)].append(member)\n",
    "        return mp\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        uf = UnionFind(n * m + 1)\n",
    "        CEIL = n * m\n",
    "        k = len(hits)\n",
    "        res = [0 for _ in range(k)]\n",
    "\n",
    "        for i, (a, b) in enumerate(hits):\n",
    "            if grid[a][b] == 1:\n",
    "                grid[a][b] = 0\n",
    "            else:\n",
    "                res[i] = -1\n",
    "        \n",
    "        d = ((1, 0), (0, 1), (-1, 0), (0, -1))\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid[x][y] == 1:\n",
    "                    # print('ufxy', x, y)\n",
    "                    for dx, dy in d:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:\n",
    "                            # print('uf', x, y, nx, ny)\n",
    "                            uf.Union(x * m + y, nx * m + ny)\n",
    "                        if nx == -1:\n",
    "                            # print('uf', x, y, CEIL)\n",
    "                            uf.Union(x * m + y, CEIL)\n",
    "        prev = uf.size[uf.Find(CEIL)] - 1\n",
    "        # print('prev', prev)\n",
    "\n",
    "        for i, (x, y) in enumerate(reversed(hits)):\n",
    "            if res[k - 1 - i] == -1:\n",
    "                res[k - 1 - i] = 0\n",
    "                continue\n",
    "            grid[x][y] = 1\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:\n",
    "                    uf.Union(x * m + y, nx * m + ny)\n",
    "                if nx == -1:\n",
    "                    uf.Union(x * m + y, CEIL)\n",
    "            new = uf.size[uf.Find(CEIL)] - 1\n",
    "            res[k - i - 1] = max(0, new - prev - 1)\n",
    "            prev = new\n",
    "            # print('new', x, y, new)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        fa = [i for i in range(m * n + 1)]\n",
    "        sz = [1 for i in range(m * n + 1)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] == i:\n",
    "                return i\n",
    "            else:\n",
    "                fa[i] = find(fa[i])\n",
    "                return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fi = find(i)\n",
    "            fj = find(j)\n",
    "\n",
    "            if fi == fj:\n",
    "                return\n",
    "\n",
    "            fa[fi] = fj\n",
    "            sz[fj] += sz[fi]\n",
    "\n",
    "        g = [[grid[i][j] for j in range(n)] for i in range(m)]\n",
    "\n",
    "        for i, j in hits:\n",
    "            g[i][j] = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j] == 0:\n",
    "                    continue\n",
    "\n",
    "                if i == 0:\n",
    "                    merge(i * n + j, m * n)\n",
    "\n",
    "                for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and g[x][y] == 1:\n",
    "                        merge(i * n + j, x * n + y)\n",
    "\n",
    "        # print(g)\n",
    "        # print(fa, sz)\n",
    "\n",
    "        ret = []\n",
    "        prev = sz[find(m * n)]\n",
    "        for i, j in reversed(hits):\n",
    "            if grid[i][j] == 0:\n",
    "                ret.append(0)\n",
    "                continue\n",
    "\n",
    "            g[i][j] = 1\n",
    "            if i == 0:\n",
    "                merge(i * n + j, m * n)\n",
    "\n",
    "            for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):\n",
    "                if 0 <= x < m and 0 <= y < n and g[x][y] == 1:\n",
    "                    merge(i * n + j, x * n + y)\n",
    "\n",
    "            # print(fa, sz)\n",
    "            cnt = sz[find(m * n)]\n",
    "            ret.append(cnt - prev - 1 if cnt > prev else 0)\n",
    "            prev = cnt\n",
    "\n",
    "        ret.reverse()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, number):\n",
    "        self.parents = [i for i in range(number)]\n",
    "        self.size = [1] * number\n",
    "\n",
    "    def find(self, index):\n",
    "        if self.parents[index] != index:\n",
    "            self.parents[index] = self.find(self.parents[index])\n",
    "        return self.parents[index]\n",
    "\n",
    "    def union(self, index1, index2):\n",
    "        parent1 = self.find(index1)\n",
    "        parent2 = self.find(index2)\n",
    "        if parent1 != parent2:\n",
    "            self.parents[parent1] = parent2\n",
    "            self.size[parent2] += self.size[parent1]\n",
    "\n",
    "    def get_size(self, index):\n",
    "        return self.size[self.find(index)]\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        wall = row * col\n",
    "        zero_index = set()\n",
    "        for i, [x, y] in enumerate(hits):\n",
    "            if grid[x][y] == 1:\n",
    "                grid[x][y] = 0\n",
    "            else:\n",
    "                zero_index.add(len(hits) - i - 1)\n",
    "        ans = []\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        unionfind = UnionFind(wall + 1)\n",
    "        for x in range(row):\n",
    "            for y in range(col):\n",
    "                if grid[x][y] == 0:\n",
    "                    continue\n",
    "                for dx, dy in directions:\n",
    "                    xx, yy = x + dx, y + dy\n",
    "                    if 0 <= xx < row and 0 <= yy < col:\n",
    "                        if grid[xx][yy] == 1:\n",
    "                            unionfind.union(x * col + y, xx * col + yy)\n",
    "                    elif xx == -1:\n",
    "                        unionfind.union(x * col + y, wall)\n",
    "        for i, [x, y] in enumerate(reversed(hits)):\n",
    "            if i in zero_index:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                grid[x][y] = 1\n",
    "                pre = unionfind.get_size(wall)\n",
    "                for dx, dy in directions:\n",
    "                    xx, yy = x + dx, y + dy\n",
    "                    if 0 <= xx < row and 0 <= yy < col:\n",
    "                        if grid[xx][yy] == 1:\n",
    "                            unionfind.union(x * col + y, xx * col + yy)\n",
    "                    elif xx == -1:\n",
    "                        unionfind.union(x * col + y, wall)\n",
    "                cur = unionfind.get_size(wall)\n",
    "                if unionfind.find(x * col + y) == unionfind.find(wall):\n",
    "                    ans.append(cur - pre - 1)\n",
    "                else:\n",
    "                    ans.append(cur - pre)\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        self.size_of_set = {}\n",
    "    \n",
    "    def get_size_of_set(self,x):\n",
    "        \"\"\"\n",
    "        获取所在连通块的大小\n",
    "        \"\"\"\n",
    "        return self.size_of_set[self.find(x)]\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            # 更新根节点连通块数量\n",
    "            self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "            del self.size_of_set[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.size_of_set[x] = 1\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.CEILING = (-1,-1)\n",
    "        self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))\n",
    "    \n",
    "    def initialize(self,uf,m,n,grid,hits):\n",
    "        \"\"\"\n",
    "        初始化\n",
    "        \"\"\"\n",
    "        # 添加天花板\n",
    "        uf.add(self.CEILING)\n",
    "        \n",
    "        # 敲掉所有要敲掉的砖块\n",
    "        for x,y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        \n",
    "        # 连接，合并剩余的砖块\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i,j))\n",
    "       \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.merge_neighbors(uf,m,n,grid,i,j)\n",
    "        \n",
    "        # 与天花板合并\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.merge((0,j),self.CEILING)\n",
    "    \n",
    "    def is_valid(self,x,y,grid,m,n):\n",
    "        return 0 <= x < m and 0 <= y < n and grid[x][y] == 1\n",
    "    \n",
    "    def merge_neighbors(self,uf,m,n,grid,x,y):\n",
    "        \"\"\"\n",
    "        与上下左右的砖块合并\n",
    "        \"\"\"\n",
    "        for dx,dy in self.DIRECTION:\n",
    "            nx,ny = x+dx,y+dy\n",
    "            if not self.is_valid(nx,ny,grid,m,n):\n",
    "                continue\n",
    "            uf.merge((x,y),(nx,ny))\n",
    "    \n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [0] * len(hits)\n",
    "        \n",
    "        # 初始化\n",
    "        self.initialize(uf,m,n,grid,hits)\n",
    "\n",
    "        for i in range(len(hits)-1,-1,-1):\n",
    "            x,y = hits[i][0],hits[i][1]\n",
    "            \n",
    "            # 还原敲击\n",
    "            grid[x][y] += 1\n",
    "            \n",
    "            # 敲的地方原本就不是砖块\n",
    "            if grid[x][y] != 1:\n",
    "                continue\n",
    "            \n",
    "            # 敲完以后与天花板连接的数量\n",
    "            after_hit = uf.get_size_of_set(self.CEILING)\n",
    "            \n",
    "            # 填回砖块，合并\n",
    "            uf.add((x,y))\n",
    "            self.merge_neighbors(uf,m,n,grid,x,y)\n",
    "            if x == 0:\n",
    "                uf.merge((x,y),self.CEILING)\n",
    "            \n",
    "            # 被敲的地方和天花板连接\n",
    "            if uf.is_connected((x,y),self.CEILING):\n",
    "                # 敲之前和天花板连接的数量\n",
    "                before_hit = uf.get_size_of_set(self.CEILING)\n",
    "                res[i] = before_hit - after_hit - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\r\n",
    "    def __init__(self):\r\n",
    "        self.father = {}\r\n",
    "        self.size_of_set = {}\r\n",
    "    \r\n",
    "    def get_size_of_set(self,x):\r\n",
    "        \"\"\"\r\n",
    "        获取所在连通块的大小\r\n",
    "        \"\"\"\r\n",
    "        return self.size_of_set[self.find(x)]\r\n",
    "    \r\n",
    "    def find(self,x):\r\n",
    "        root = x\r\n",
    "        \r\n",
    "        while self.father[root] != None:\r\n",
    "            root = self.father[root]\r\n",
    "        \r\n",
    "        # 路径压缩\r\n",
    "        while x != root:\r\n",
    "            original_father = self.father[x]\r\n",
    "            self.father[x] = root\r\n",
    "            x = original_father\r\n",
    "        \r\n",
    "        return root\r\n",
    "    \r\n",
    "    def is_connected(self,x,y):\r\n",
    "        return self.find(x) == self.find(y)\r\n",
    "    \r\n",
    "    def merge(self,x,y):\r\n",
    "        root_x,root_y = self.find(x),self.find(y)\r\n",
    "        \r\n",
    "        if root_x != root_y:\r\n",
    "            self.father[root_x] = root_y\r\n",
    "            # 更新根节点连通块数量\r\n",
    "            self.size_of_set[root_y] += self.size_of_set[root_x]\r\n",
    "            del self.size_of_set[root_x]\r\n",
    "    \r\n",
    "    def add(self,x):\r\n",
    "        if x not in self.father:\r\n",
    "            self.father[x] = None\r\n",
    "            self.size_of_set[x] = 1\r\n",
    "            \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def __init__(self):\r\n",
    "        self.CEILING = (-1,-1)\r\n",
    "        self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))\r\n",
    "    \r\n",
    "    def initialize(self,uf,m,n,grid,hits):\r\n",
    "        \"\"\"\r\n",
    "        初始化\r\n",
    "        \"\"\"\r\n",
    "        # 添加天花板\r\n",
    "        uf.add(self.CEILING)\r\n",
    "        \r\n",
    "        # 敲掉所有要敲掉的砖块\r\n",
    "        for x,y in hits:\r\n",
    "            grid[x][y] -= 1\r\n",
    "        \r\n",
    "        # 连接，合并剩余的砖块\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == 1:\r\n",
    "                    uf.add((i,j))\r\n",
    "       \r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == 1:\r\n",
    "                    self.merge_neighbors(uf,m,n,grid,i,j)\r\n",
    "        \r\n",
    "        # 与天花板合并\r\n",
    "        for j in range(n):\r\n",
    "            if grid[0][j] == 1:\r\n",
    "                uf.merge((0,j),self.CEILING)\r\n",
    "    \r\n",
    "    def is_valid(self,x,y,grid,m,n):\r\n",
    "        return 0 <= x < m and 0 <= y < n and grid[x][y] == 1\r\n",
    "    \r\n",
    "    def merge_neighbors(self,uf,m,n,grid,x,y):\r\n",
    "        \"\"\"\r\n",
    "        与上下左右的砖块合并\r\n",
    "        \"\"\"\r\n",
    "        for dx,dy in self.DIRECTION:\r\n",
    "            nx,ny = x+dx,y+dy\r\n",
    "            if not self.is_valid(nx,ny,grid,m,n):\r\n",
    "                continue\r\n",
    "            uf.merge((x,y),(nx,ny))\r\n",
    "    \r\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\r\n",
    "        uf = UnionFind()\r\n",
    "        m,n = len(grid),len(grid[0])\r\n",
    "        res = [0] * len(hits)\r\n",
    "        \r\n",
    "        # 初始化\r\n",
    "        self.initialize(uf,m,n,grid,hits)\r\n",
    "\r\n",
    "        for i in range(len(hits)-1,-1,-1):\r\n",
    "            x,y = hits[i][0],hits[i][1]\r\n",
    "            \r\n",
    "            # 还原敲击\r\n",
    "            grid[x][y] += 1\r\n",
    "            \r\n",
    "            # 敲的地方原本就不是砖块\r\n",
    "            if grid[x][y] != 1:\r\n",
    "                continue\r\n",
    "            \r\n",
    "            # 敲完以后与天花板连接的数量\r\n",
    "            after_hit = uf.get_size_of_set(self.CEILING)\r\n",
    "            \r\n",
    "            # 填回砖块，合并\r\n",
    "            uf.add((x,y))\r\n",
    "            self.merge_neighbors(uf,m,n,grid,x,y)\r\n",
    "            if x == 0:\r\n",
    "                uf.merge((x,y),self.CEILING)\r\n",
    "            \r\n",
    "            # 被敲的地方和天花板连接\r\n",
    "            if uf.is_connected((x,y),self.CEILING):\r\n",
    "                # 敲之前和天花板连接的数量\r\n",
    "                before_hit = uf.get_size_of_set(self.CEILING)\r\n",
    "                res[i] = before_hit - after_hit - 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        self.size_of_set = {}\n",
    "    \n",
    "    def get_size_of_set(self,x):\n",
    "        \"\"\"\n",
    "        获取所在连通块的大小\n",
    "        \"\"\"\n",
    "        return self.size_of_set[self.find(x)]\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            # 更新根节点连通块数量\n",
    "            self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "            del self.size_of_set[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.size_of_set[x] = 1\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.CEILING = (-1,-1)\n",
    "        self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))\n",
    "    \n",
    "    def initialize(self,uf,m,n,grid,hits):\n",
    "        \"\"\"\n",
    "        初始化\n",
    "        \"\"\"\n",
    "        # 添加天花板\n",
    "        uf.add(self.CEILING)\n",
    "        \n",
    "        # 敲掉所有要敲掉的砖块\n",
    "        for x,y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        \n",
    "        # 连接，合并剩余的砖块\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i,j))\n",
    "       \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.merge_neighbors(uf,m,n,grid,i,j)\n",
    "        \n",
    "        # 与天花板合并\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.merge((0,j),self.CEILING)\n",
    "    \n",
    "    def is_valid(self,x,y,grid,m,n):\n",
    "        return 0 <= x < m and 0 <= y < n and grid[x][y] == 1\n",
    "    \n",
    "    def merge_neighbors(self,uf,m,n,grid,x,y):\n",
    "        \"\"\"\n",
    "        与上下左右的砖块合并\n",
    "        \"\"\"\n",
    "        for dx,dy in self.DIRECTION:\n",
    "            nx,ny = x+dx,y+dy\n",
    "            if not self.is_valid(nx,ny,grid,m,n):\n",
    "                continue\n",
    "            uf.merge((x,y),(nx,ny))\n",
    "    \n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [0] * len(hits)\n",
    "        \n",
    "        # 初始化\n",
    "        self.initialize(uf,m,n,grid,hits)\n",
    "\n",
    "        for i in range(len(hits)-1,-1,-1):\n",
    "            x,y = hits[i][0],hits[i][1]\n",
    "            \n",
    "            # 还原敲击\n",
    "            grid[x][y] += 1\n",
    "            \n",
    "            # 敲的地方原本就不是砖块\n",
    "            if grid[x][y] != 1:\n",
    "                continue\n",
    "            \n",
    "            # 敲完以后与天花板连接的数量\n",
    "            after_hit = uf.get_size_of_set(self.CEILING)\n",
    "            \n",
    "            # 填回砖块，合并\n",
    "            uf.add((x,y))\n",
    "            self.merge_neighbors(uf,m,n,grid,x,y)\n",
    "            if x == 0:\n",
    "                uf.merge((x,y),self.CEILING)\n",
    "            \n",
    "            # 被敲的地方和天花板连接\n",
    "            if uf.is_connected((x,y),self.CEILING):\n",
    "                # 敲之前和天花板连接的数量\n",
    "                before_hit = uf.get_size_of_set(self.CEILING)\n",
    "                res[i] = before_hit - after_hit - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.father = {}\n",
    "        self.size_of_set = {}\n",
    "    \n",
    "    def get_size_of_set(self,x):\n",
    "        \"\"\"\n",
    "        获取所在连通块的大小\n",
    "        \"\"\"\n",
    "        return self.size_of_set[self.find(x)]\n",
    "    \n",
    "    def find(self,x):\n",
    "        root = x\n",
    "        \n",
    "        while self.father[root] != None:\n",
    "            root = self.father[root]\n",
    "        \n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        root_x,root_y = self.find(x),self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.father[root_x] = root_y\n",
    "            # 更新根节点连通块数量\n",
    "            self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "            del self.size_of_set[root_x]\n",
    "    \n",
    "    def add(self,x):\n",
    "        if x not in self.father:\n",
    "            self.father[x] = None\n",
    "            self.size_of_set[x] = 1\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.CEILING = (-1,-1)\n",
    "        self.DIRECTION = ((1,0),(-1,0),(0,1),(0,-1))\n",
    "    \n",
    "    def initialize(self,uf,m,n,grid,hits):\n",
    "        \"\"\"\n",
    "        初始化\n",
    "        \"\"\"\n",
    "        # 添加天花板\n",
    "        uf.add(self.CEILING)\n",
    "        \n",
    "        # 敲掉所有要敲掉的砖块\n",
    "        for x,y in hits:\n",
    "            grid[x][y] -= 1\n",
    "        \n",
    "        # 连接，合并剩余的砖块\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i,j))\n",
    "       \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.merge_neighbors(uf,m,n,grid,i,j)\n",
    "        \n",
    "        # 与天花板合并\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.merge((0,j),self.CEILING)\n",
    "    \n",
    "    def is_valid(self,x,y,grid,m,n):\n",
    "        return 0 <= x < m and 0 <= y < n and grid[x][y] == 1\n",
    "    \n",
    "    def merge_neighbors(self,uf,m,n,grid,x,y):\n",
    "        \"\"\"\n",
    "        与上下左右的砖块合并\n",
    "        \"\"\"\n",
    "        for dx,dy in self.DIRECTION:\n",
    "            nx,ny = x+dx,y+dy\n",
    "            if not self.is_valid(nx,ny,grid,m,n):\n",
    "                continue\n",
    "            uf.merge((x,y),(nx,ny))\n",
    "    \n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [0] * len(hits)\n",
    "        \n",
    "        # 初始化\n",
    "        self.initialize(uf,m,n,grid,hits)\n",
    "\n",
    "        for i in range(len(hits)-1,-1,-1):\n",
    "            x,y = hits[i][0],hits[i][1]\n",
    "            \n",
    "            # 还原敲击\n",
    "            grid[x][y] += 1\n",
    "            \n",
    "            # 敲的地方原本就不是砖块\n",
    "            if grid[x][y] != 1:\n",
    "                continue\n",
    "            \n",
    "            # 敲完以后与天花板连接的数量\n",
    "            after_hit = uf.get_size_of_set(self.CEILING)\n",
    "            \n",
    "            # 填回砖块，合并\n",
    "            uf.add((x,y))\n",
    "            self.merge_neighbors(uf,m,n,grid,x,y)\n",
    "            if x == 0:\n",
    "                uf.merge((x,y),self.CEILING)\n",
    "            \n",
    "            # 被敲的地方和天花板连接\n",
    "            if uf.is_connected((x,y),self.CEILING):\n",
    "                # 敲之前和天花板连接的数量\n",
    "                before_hit = uf.get_size_of_set(self.CEILING)\n",
    "                res[i] = before_hit - after_hit - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unionbrick:\n",
    "    def __init__(self, grid):\n",
    "        self.m, self.n = len(grid), len(grid[0])\n",
    "        self.father = {}\n",
    "        self.VARIABLE = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        self.size = [[0 for _ in range(self.n)] for __ in range(self.m)]\n",
    "        self.first_row = 0\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "\n",
    "        while self.father[root] != root:\n",
    "            root = self.father[root]\n",
    "\n",
    "        # 路径压缩\n",
    "        while x != root:\n",
    "            original_father = self.father[x]\n",
    "            self.father[x] = root\n",
    "            x = original_father\n",
    "\n",
    "        return root\n",
    "\n",
    "    def find_size(self,x: tuple):\n",
    "        return self.size[x[0]][x[1]]\n",
    "\n",
    "    def merge(self, x: tuple, y: tuple):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        #sx, sy = self.size[root_x[0]][root_x[1]], self.size[root_y[0]][root_y[1]]\n",
    "        if root_x != root_y:\n",
    "            if root_y[0] == 0:\n",
    "                self.father[root_x] = root_y\n",
    "                self.size[root_y[0]][root_y[1]] += self.size[root_x[0]][root_x[1]]\n",
    "                self.size[root_x[0]][root_x[1]] = 0\n",
    "            else:\n",
    "                self.father[root_y] = root_x\n",
    "                self.size[root_x[0]][root_x[1]] += self.size[root_y[0]][root_y[1]]\n",
    "                self.size[root_y[0]][root_y[1]] = 0\n",
    "                \n",
    "    def _add(self, x):\n",
    "        self.father[x] = x\n",
    "        self.size[x[0]][x[1]] = 1\n",
    "\n",
    "    def dfs(self, x, y, s: set, grid):\n",
    "        for a, b in self.VARIABLE:\n",
    "            nx, ny = x + a, y + b\n",
    "            if 0 < nx < self.m and 0 <= ny < self.n and (nx, ny) not in s and grid[nx][ny] == 1:\n",
    "                self._add((nx,ny))\n",
    "                self.merge((x, y), (nx, ny))\n",
    "                s.add((nx, ny))\n",
    "                self.dfs(nx, ny, s, grid)\n",
    "\n",
    "    def _update(self, x, y, grid1):\n",
    "        self._add((x, y))\n",
    "        for a, b in self.VARIABLE:\n",
    "            nx, ny = x + a, y + b\n",
    "            if 0 <= nx < self.m and 0 <= ny < self.n and grid1[nx][ny] == 1:\n",
    "                self.merge((x, y), (nx, ny))\n",
    "\n",
    "    def count_bricks(self):\n",
    "        return sum(self.size[0]) - self.first_row\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid, hits):\n",
    "        grid1 = copy.deepcopy(grid)\n",
    "        for hit in hits:\n",
    "            grid1[hit[0]][hit[1]] = 0\n",
    "        unionbrick = Unionbrick(grid1)\n",
    "        print(grid1)\n",
    "        s = set()\n",
    "        for i in range(unionbrick.n):  # 对屋顶石子进行合并\n",
    "            if grid1[0][i] == 1:\n",
    "                unionbrick.first_row += 1\n",
    "                unionbrick._add((0, i))\n",
    "                unionbrick.dfs(0, i, s, grid1)\n",
    "        origin = len(s)  # 初始的连接到屋顶的石子数量\n",
    "        for i in range(1, unionbrick.m):  # 对其他没有连接到屋顶的石子进行合并\n",
    "            for j in range(unionbrick.n):\n",
    "                if grid1[i][j] == 1 and (i, j) not in s:\n",
    "                    s.add((i,j))\n",
    "                    unionbrick._add((i, j))\n",
    "                    unionbrick.dfs(i, j, s, grid1)\n",
    "        ans = [0 for _ in range(len(hits))]\n",
    "        for i in range(len(hits) - 1, -1, -1):\n",
    "            x, y = hits[i][0], hits[i][1]\n",
    "            if grid[x][y] == 0: continue\n",
    "            grid1[x][y] = 1\n",
    "            unionbrick._update(x, y, grid1)\n",
    "            if x == 0:\n",
    "                unionbrick.first_row += 1\n",
    "                current = unionbrick.count_bricks()\n",
    "                ans[i] = max(0, current - origin)\n",
    "            else:\n",
    "                current = unionbrick.count_bricks()\n",
    "                ans[i] = max(0, current - origin - 1)\n",
    "            origin = current\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        parent = {i : i for i in range(m * n + 1)}\n",
    "        size = [1] * (m * n + 1)\n",
    "        def find(node):\n",
    "            path = []\n",
    "            while node != parent[node]:\n",
    "                path.append(node)\n",
    "                node = parent[node]\n",
    "            for p in path:\n",
    "                parent[p] = node\n",
    "            return node\n",
    "        \n",
    "        def union(n1, n2):\n",
    "            p1 = find(n1)\n",
    "            p2 = find(n2)\n",
    "            if p1 != p2:\n",
    "                if p1 < p2:\n",
    "                    parent[p1] = p2 \n",
    "                    size[p2] += size[p1]\n",
    "                else:\n",
    "                    parent[p2] = p1 \n",
    "                    size[p1] += size[p2]\n",
    "        \n",
    "        A = [row[:] for row in grid]\n",
    "        for i, j in hits:\n",
    "            if grid[i][j] == 1:\n",
    "                A[i][j] = 0 \n",
    "        def neigh(i, j):\n",
    "            for d in ((-1, 0), (0, - 1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    yield x, y\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if A[i][j] == 1:\n",
    "                    for x, y in neigh(i, j):\n",
    "                        if A[x][y] == 1:\n",
    "                            union(i * n + j, x * n + y)\n",
    "                    if i == 0:\n",
    "                        union(i * n + j, m * n) \n",
    "        res = []\n",
    "        for i, j in hits[::-1]:\n",
    "            if grid[i][j] == 0:\n",
    "                res.append(0)\n",
    "                continue  \n",
    "            pre = size[-1]\n",
    "            A[i][j] = 1 \n",
    "            for x, y in neigh(i, j):\n",
    "                if A[x][y] == 1:\n",
    "                    union(i * n + j, x * n + y)\n",
    "            if i == 0:\n",
    "                union(i * n + j, m * n)  \n",
    "            res.append(max(0, size[-1] - pre - 1))\n",
    "        return res[::-1]\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        # remove the knocked bricks\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for hit in hits:\n",
    "            grid[hit[0]][hit[1]] -= 1\n",
    "\n",
    "        uf = UnionFind()\n",
    "        uf.add((-1, -1))\n",
    "    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i, j))\n",
    "        # 将直接贴墙的砖合并到墙上\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.union((0, j), (-1, -1))\n",
    "        # 所有砖和邻居合并\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if grid[i - 1][j] == 1:\n",
    "                        uf.union((i, j), (i - 1, j))\n",
    "                    if j - 1 >= 0 and grid[i][j - 1] == 1:\n",
    "                        uf.union((i, j), (i, j - 1))   \n",
    "        result = []\n",
    "        for i, j in hits[::-1]:\n",
    "            # edge case:敲击的砖块本来就为空\n",
    "            if grid[i][j] != 0:\n",
    "                result.append(0)\n",
    "                continue\n",
    "            pre = uf.get_size((-1, -1)) - 1\n",
    "            uf.add((i, j))\n",
    "            if i == 0:\n",
    "                uf.union((i, j), (-1, -1))\n",
    "                print(uf.get_size((-1,-1)) - 1)\n",
    "            for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < len(grid) and 0 <= jj < len(grid[0]) and grid[ii][jj] == 1:\n",
    "                    uf.union((ii, jj), (i, j))\n",
    "                    \n",
    "            current = uf.get_size((-1, -1)) - 1\n",
    "            result.append(max(0, current - pre - 1))\n",
    "            grid[i][j] = 1\n",
    "        return result[::-1]\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size_of_set = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        self.parent[x] = x\n",
    "        self.size_of_set[x] = 1\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self.parent[root] != root:\n",
    "            root = self.parent[root]\n",
    "        \n",
    "        while self.parent[x] != x:\n",
    "            temp = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = temp\n",
    "        return root\n",
    "\n",
    "    def get_size(self, x):\n",
    "        return self.size_of_set[self.find(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        # remove the knocked bricks\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for hit in hits:\n",
    "            grid[hit[0]][hit[1]] -= 1\n",
    "\n",
    "        uf = UnionFind()\n",
    "        uf.add((-1, -1))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i, j))\n",
    "        # 将直接贴墙的砖合并到墙上\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.union((0, j), (-1, -1))\n",
    "        # 所有砖和邻居合并\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if grid[i - 1][j] == 1:\n",
    "                        uf.union((i, j), (i - 1, j))\n",
    "                    if j - 1 >= 0 and grid[i][j - 1] == 1:\n",
    "                        uf.union((i, j), (i, j - 1))   \n",
    "        result = []\n",
    "        for i, j in hits[::-1]:\n",
    "            # edge case:敲击的砖块本来就为空\n",
    "            if grid[i][j] != 0:\n",
    "                result.append(0)\n",
    "                continue\n",
    "            pre = uf.get_size((-1, -1)) - 1\n",
    "            uf.add((i, j))\n",
    "            if i == 0:\n",
    "                uf.union((i, j), (-1, -1))\n",
    "\n",
    "            for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < len(grid) and 0 <= jj < len(grid[0]) and grid[ii][jj] == 1:\n",
    "                    uf.union((ii, jj), (i, j))\n",
    "                    \n",
    "            current = uf.get_size((-1, -1)) - 1\n",
    "            result.append(max(0, current - pre - 1))\n",
    "            grid[i][j] = 1\n",
    "        return result[::-1]\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size_of_set = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        self.parent[x] = x\n",
    "        self.size_of_set[x] = 1\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self.parent[root] != root:\n",
    "            root = self.parent[root]\n",
    "        \n",
    "        while self.parent[x] != x:\n",
    "            temp = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = temp\n",
    "        return root\n",
    "\n",
    "    def get_size(self, x):\n",
    "        return self.size_of_set[self.find(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        # remove the knocked bricks\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for hit in hits:\n",
    "            grid[hit[0]][hit[1]] -= 1\n",
    "\n",
    "        uf = UnionFind()\n",
    "        uf.add((-1, -1))\n",
    "    \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    uf.add((i, j))\n",
    "        # 将直接贴墙的砖合并到墙上\n",
    "        for j in range(n):\n",
    "            if grid[0][j] == 1:\n",
    "                uf.union((0, j), (-1, -1))\n",
    "        # 所有砖和邻居合并\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if grid[i - 1][j] == 1:\n",
    "                        uf.union((i, j), (i - 1, j))\n",
    "                    if j - 1 >= 0 and grid[i][j - 1] == 1:\n",
    "                        uf.union((i, j), (i, j - 1))   \n",
    "        result = []\n",
    "        for i, j in hits[::-1]:\n",
    "            # edge case:敲击的砖块本来就为空\n",
    "            if grid[i][j] != 0:\n",
    "                result.append(0)\n",
    "                continue\n",
    "            pre = uf.get_size((-1, -1)) - 1\n",
    "            print('pre',i, j, pre)\n",
    "            uf.add((i, j))\n",
    "            print('add',i, j, uf.get_size((-1, -1)) - 1)\n",
    "            if i == 0:\n",
    "                uf.union((i, j), (-1, -1))\n",
    "                print(uf.get_size((-1,-1)) - 1)\n",
    "            for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                ii, jj = i + di, j + dj\n",
    "                if 0 <= ii < len(grid) and 0 <= jj < len(grid[0]) and grid[ii][jj] == 1:\n",
    "                    uf.union((ii, jj), (i, j))\n",
    "                    print(ii, jj, uf.get_size((-1, -1)) - 1)\n",
    "                    \n",
    "            current = uf.get_size((-1, -1)) - 1\n",
    "            print('current', current)\n",
    "            result.append(max(0, current - pre - 1))\n",
    "            grid[i][j] = 1\n",
    "        return result[::-1]\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size_of_set = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        self.parent[x] = x\n",
    "        self.size_of_set[x] = 1\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return\n",
    "        self.parent[root_x] = root_y\n",
    "        self.size_of_set[root_y] += self.size_of_set[root_x]\n",
    "\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self.parent[root] != root:\n",
    "            root = self.parent[root]\n",
    "        \n",
    "        while self.parent[x] != x:\n",
    "            temp = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = temp\n",
    "        return root\n",
    "\n",
    "    def get_size(self, x):\n",
    "        return self.size_of_set[self.find(x)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, n, m):\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.list = {}\n",
    "        self.rank = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                self.list[(i, j)] = (i, j)\n",
    "                self.rank[(i, j)] = 0\n",
    "        self.list[(-1, -1)] = (-1, -1)\n",
    "        self.rank[(-1, -1)] = 1\n",
    "\n",
    "    \n",
    "    def find(self, site):\n",
    "        if self.list[site] == site:\n",
    "            return site\n",
    "        temp = self.find(self.list[site])\n",
    "        self.list[site] = temp\n",
    "        return self.list[site]\n",
    "    \n",
    "    def union(self, site1, site2):\n",
    "        mom1 = self.find(site1)\n",
    "        mom2 = self.find(site2)\n",
    "        if mom1 == mom2:\n",
    "            return\n",
    "        if mom1[0] < mom2[0]:\n",
    "            self.list[mom2] = mom1\n",
    "            self.rank[mom1] += self.rank[mom2]\n",
    "            self.rank[mom2] = 0\n",
    "        else:\n",
    "            self.list[mom1] = mom2\n",
    "            self.rank[mom2] += self.rank[mom1]\n",
    "            self.rank[mom1] = 0\n",
    "    \n",
    "    def p(self):\n",
    "        # print(self.list[(-1, -1)])\n",
    "        # for i in range(self.n):\n",
    "        #     for j in range(self.m):\n",
    "        #         print(self.list[(i, j)], end='\\t')\n",
    "        #     print()\n",
    "        \n",
    "        print(self.rank[(-1, -1)])\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.m):\n",
    "                print(self.rank[(i, j)], end='\\t')\n",
    "            print()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        n, m  = len(grid), len(grid[0])\n",
    "        aspect = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        tree = Tree(n, m)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    tree.rank[(i, j)] = 1\n",
    "\n",
    "        isgood = set()\n",
    "        for x, y in hits:\n",
    "            if grid[x][y]:\n",
    "                isgood.add((x, y))\n",
    "            grid[x][y] = 0\n",
    "        \n",
    "        \n",
    "        # 并查集的初始链接\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 跟房顶合并\n",
    "                    if i == 0:\n",
    "                        tree.union((i, j), (-1, -1))\n",
    "                    for a, b in aspect:\n",
    "                        a += i\n",
    "                        b += j\n",
    "                        if 0 <= a < n and 0 <= b < m and grid[a][b] == 1:\n",
    "                            tree.union((i, j), (a, b))\n",
    "        # tree.p()\n",
    "\n",
    "\n",
    "        n2 = len(hits)\n",
    "        result = [0 for _ in range(n2)]\n",
    "        for i in range(n2 - 1, -1, -1):\n",
    "            # print(\"-------------\", hits[i])\n",
    "            x, y = hits[i]\n",
    "            if (x, y) in isgood:\n",
    "                grid[x][y] = 1\n",
    "                temp = tree.rank[(-1, -1)]\n",
    "\n",
    "                if x == 0:\n",
    "                    tree.union((x, y), (-1, -1))\n",
    "\n",
    "                for a, b in aspect:\n",
    "                    a += x\n",
    "                    b += y\n",
    "                    if 0 <= a < n and 0 <= b < m and grid[a][b] == 1:\n",
    "                        tree.union((x, y), (a, b))\n",
    "                result[i] = max(0, tree.rank[(-1, -1)] - temp - 1)\n",
    "                # tree.p()\n",
    "        return result\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self, n, m):\n",
    "        self.n = n\n",
    "        self.m = m\n",
    "        self.list = {}\n",
    "        self.rank = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                self.list[(i, j)] = (i, j)\n",
    "                self.rank[(i, j)] = 0\n",
    "        self.list[(-1, -1)] = (-1, -1)\n",
    "        self.rank[(-1, -1)] = 1\n",
    "\n",
    "    \n",
    "    def find(self, site):\n",
    "        if self.list[site] == site:\n",
    "            return site\n",
    "        temp = self.find(self.list[site])\n",
    "        self.list[site] = temp\n",
    "        return self.list[site]\n",
    "    \n",
    "    def union(self, site1, site2):\n",
    "        mom1 = self.find(site1)\n",
    "        mom2 = self.find(site2)\n",
    "        if mom1 == mom2:\n",
    "            return\n",
    "        if mom1[0] < mom2[0]:\n",
    "            self.list[mom2] = mom1\n",
    "            self.rank[mom1] += self.rank[mom2]\n",
    "            self.rank[mom2] = 0\n",
    "        else:\n",
    "            self.list[mom1] = mom2\n",
    "            self.rank[mom2] += self.rank[mom1]\n",
    "            self.rank[mom1] = 0\n",
    "    \n",
    "    def p(self):\n",
    "        # print(self.list[(-1, -1)])\n",
    "        # for i in range(self.n):\n",
    "        #     for j in range(self.m):\n",
    "        #         print(self.list[(i, j)], end='\\t')\n",
    "        #     print()\n",
    "        \n",
    "        print(self.rank[(-1, -1)])\n",
    "        for i in range(self.n):\n",
    "            for j in range(self.m):\n",
    "                print(self.rank[(i, j)], end='\\t')\n",
    "            print()\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        n, m  = len(grid), len(grid[0])\n",
    "        aspect = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "\n",
    "        tree = Tree(n, m)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]:\n",
    "                    tree.rank[(i, j)] = 1\n",
    "\n",
    "        isgood = set()\n",
    "        for x, y in hits:\n",
    "            if grid[x][y]:\n",
    "                isgood.add((x, y))\n",
    "            grid[x][y] = 0\n",
    "        \n",
    "        \n",
    "        # 并查集的初始链接\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 跟房顶合并\n",
    "                    if i == 0:\n",
    "                        tree.union((i, j), (-1, -1))\n",
    "                    for a, b in aspect:\n",
    "                        a += i\n",
    "                        b += j\n",
    "                        if 0 <= a < n and 0 <= b < m and grid[a][b] == 1:\n",
    "                            tree.union((i, j), (a, b))\n",
    "        tree.p()\n",
    "\n",
    "\n",
    "        n2 = len(hits)\n",
    "        result = [0 for _ in range(n2)]\n",
    "        for i in range(n2 - 1, -1, -1):\n",
    "            # print(\"-------------\", hits[i])\n",
    "            x, y = hits[i]\n",
    "            if (x, y) in isgood:\n",
    "                grid[x][y] = 1\n",
    "                temp = tree.rank[(-1, -1)]\n",
    "\n",
    "                if x == 0:\n",
    "                    tree.union((x, y), (-1, -1))\n",
    "\n",
    "                for a, b in aspect:\n",
    "                    a += x\n",
    "                    b += y\n",
    "                    if 0 <= a < n and 0 <= b < m and grid[a][b] == 1:\n",
    "                        tree.union((x, y), (a, b))\n",
    "                result[i] = max(0, tree.rank[(-1, -1)] - temp - 1)\n",
    "                # tree.p()\n",
    "        return result\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:\n",
    "        my_grid = np.array(grid)\n",
    "        res = []\n",
    "        # 得到去掉所有块后的稳定grid\n",
    "        new_grid, last_grid = func2(my_grid, hits)\n",
    "        height, width = my_grid.shape\n",
    "        for i in range(len(hits)-1, -1, -1):\n",
    "            y0, x0 = hits[i]\n",
    "            # 本来不是1的，那直接不用填了\n",
    "            if my_grid[y0, x0] == 0:\n",
    "                res = [0] + res\n",
    "                continue\n",
    "            # 本来是1的， 填进去\n",
    "            \n",
    "            new_grid[y0, x0] = 1\n",
    "            # 看看他放上去后是不是稳定的\n",
    "            if not is_stable(x0, y0, last_grid):\n",
    "                res = [0] + res\n",
    "                continue\n",
    "            last_grid[y0, x0] = 1\n",
    "            \n",
    "            # 能稳定下来，就看他还能生长多少\n",
    "            pending = [(x0, y0)]\n",
    "            num = 0\n",
    "            while pending:\n",
    "                x0, y0 = pending.pop()\n",
    "                for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                    x = x0 + dx\n",
    "                    y = y0 + dy\n",
    "                    if x < 0 or x >= width or y < 0 or y >= height:\n",
    "                        continue\n",
    "                    if new_grid[y, x] == 1 and last_grid[y, x] != 1:\n",
    "                        pending.append((x, y))\n",
    "                        last_grid[y, x] = 1\n",
    "                        num += 1\n",
    "            res = [num] + res\n",
    "        return res\n",
    "\n",
    "def is_stable(x0, y0, last_grid):\n",
    "    if y0 == 0:\n",
    "        return True\n",
    "    height, width = last_grid.shape\n",
    "    for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "        x = x0 + dx\n",
    "        y = y0 + dy\n",
    "        if x < 0 or x >= width or y < 0 or y >= height:\n",
    "            continue\n",
    "        if last_grid[y, x] == 1:\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def func2(my_grid, hits):\n",
    "    new_grid = my_grid.copy()\n",
    "    for y, x in hits:\n",
    "        new_grid[y, x] = 0\n",
    "\n",
    "    height, width = new_grid.shape\n",
    "    res = np.zeros_like(new_grid)\n",
    "    pending = [(i, 0) for i in range(width) if new_grid[0, i] == 1]\n",
    "    res[0] = new_grid[0]\n",
    "    while pending:\n",
    "        x0, y0 = pending.pop()\n",
    "        for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "            x = x0 + dx\n",
    "            y = y0 + dy\n",
    "            if x < 0 or x >= width or y < 0 or y >= height:\n",
    "                continue\n",
    "            if new_grid[y, x] == 1 and res[y, x] != 1:\n",
    "                pending.append((x, y))\n",
    "                res[y, x] = 1\n",
    "    return new_grid, res\n",
    "\n",
    "\n",
    "    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
